/*------------------------------------------------------------------------
 *
 * geqo_main.c
 *	  通过遗传算法（GA）来解决查询优化问题
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/backend/optimizer/geqo/geqo_main.c
 *
 *-------------------------------------------------------------------------
 */

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* -- 这部分的内容改编自 D. Whitley 的 Genitor 算法 -- */

#include "postgres.h"

#include <math.h>

#include "optimizer/geqo_misc.h"
#include "optimizer/geqo_mutation.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_selection.h"


/*
 * 配置选项
 */
int			Geqo_effort;
int			Geqo_pool_size;
int			Geqo_generations;
double		Geqo_selection_bias;
double		Geqo_seed;


static int	fc_gimme_pool_size(int fc_nr_rel);
static int	fc_gimme_number_generations(int fc_pool_size);


/* 如果没有定义重组机制则抱怨 */
#if !defined(ERX) && \
	!defined(PMX) && \
	!defined(CX)  && \
	!defined(PX)  && \
	!defined(OX1) && \
	!defined(OX2)
#error "must choose one GEQO recombination mechanism in geqo.h"
#endif


/*
 * geqo
 *	  查询优化问题的解决方案
 *	  类似于一个约束的旅行推销员问题 (TSP)
 */

RelOptInfo * geqo(PlannerInfo *fc_root, int fc_number_of_rels, List *fc_initial_rels)
{
	GeqoPrivateData fc_private;
	int			fc_generation;
	Chromosome *fc_momma;
	Chromosome *fc_daddy;
	Chromosome *fc_kid;
	Pool	   *fc_pool;
	int			fc_pool_size,
				fc_number_generations;

#ifdef GEQO_DEBUG
	int			fc_status_interval;
#endif
	Gene	   *fc_best_tour;
	RelOptInfo *fc_best_rel;

#if defined(ERX)
	Edge	   *fc_edge_table;		/* 边的列表 */
	int			fc_edge_failures = 0;
#endif
#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
	City	   *fc_city_table;		/* 城市列表 */
#endif
#if defined(CX)
	int			fc_cycle_diffs = 0;
	int			fc_mutations = 0;
#endif

/* 设置私有信息 */
	fc_root->join_search_private = (void *) &fc_private;
	fc_private.initial_rels = fc_initial_rels;

/* 初始化私有数字生成器 */
	geqo_set_seed(fc_root, Geqo_seed);

/* 设置GA参数 */
	fc_pool_size = fc_gimme_pool_size(fc_number_of_rels);
	fc_number_generations = fc_gimme_number_generations(fc_pool_size);
#ifdef GEQO_DEBUG
	fc_status_interval = 10;
#endif

/* 分配遗传池内存 */
	fc_pool = alloc_pool(fc_root, fc_pool_size, fc_number_of_rels);

/* 遗传池的随机初始化 */
	random_init_pool(fc_root, fc_pool);

/* 根据最便宜路径对池进行排序作为适应度 */
	sort_pool(fc_root, fc_pool);		/* 我们只需要做一次，因为所有孩子将在未来替换最差个体 
								 * （-> geqo_pool.c:spread_chromo ) */

#ifdef GEQO_DEBUG
	elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
		 fc_pool_size,
		 fc_pool->data[0].worth,
		 fc_pool->data[fc_pool_size - 1].worth);
#endif

/* 分配染色体母体和父体内存 */
	fc_momma = alloc_chromo(fc_root, fc_pool->string_length);
	fc_daddy = alloc_chromo(fc_root, fc_pool->string_length);

#if defined (ERX)
#ifdef GEQO_DEBUG
	elog(DEBUG2, "using edge recombination crossover [ERX]");
#endif
/* 分配边表内存 */
	fc_edge_table = alloc_edge_table(fc_root, fc_pool->string_length);
#elif defined(PMX)
#ifdef GEQO_DEBUG
	elog(DEBUG2, "using partially matched crossover [PMX]");
#endif
/* 分配染色体孩子内存 */
	fc_kid = alloc_chromo(fc_root, fc_pool->string_length);
#elif defined(CX)
#ifdef GEQO_DEBUG
	elog(DEBUG2, "using cycle crossover [CX]");
#endif
/* 分配城市表内存 */
	fc_kid = alloc_chromo(fc_root, fc_pool->string_length);
	city_table = alloc_city_table(fc_root, fc_pool->string_length);
#elif defined(PX)
#ifdef GEQO_DEBUG
	elog(DEBUG2, "using position crossover [PX]");
#endif
/* 分配城市表内存 */
	fc_kid = alloc_chromo(fc_root, fc_pool->string_length);
	city_table = alloc_city_table(fc_root, fc_pool->string_length);
#elif defined(OX1)
#ifdef GEQO_DEBUG
	elog(DEBUG2, "using order crossover [OX1]");
#endif
/* 分配城市表内存 */
	fc_kid = alloc_chromo(fc_root, fc_pool->string_length);
	city_table = alloc_city_table(fc_root, fc_pool->string_length);
#elif defined(OX2)
#ifdef GEQO_DEBUG
	elog(DEBUG2, "using order crossover [OX2]");
#endif
/* 分配城市表内存 */
	fc_kid = alloc_chromo(fc_root, fc_pool->string_length);
	city_table = alloc_city_table(fc_root, fc_pool->string_length);
#endif


/* 我的痛苦主要部分： */
/* 迭代优化 */

	for (fc_generation = 0; fc_generation < fc_number_generations; fc_generation++)
	{
		/* 选择：使用线性偏差函数 */
		geqo_selection(fc_root, fc_momma, fc_daddy, fc_pool, Geqo_selection_bias);

#if defined (ERX)
		/* 边重组交叉 */
		gimme_edge_table(fc_root, fc_momma->string, fc_daddy->string, fc_pool->string_length, fc_edge_table);

		fc_kid = fc_momma;

		/* 有边故障吗？ */
		fc_edge_failures += gimme_tour(fc_root, fc_edge_table, fc_kid->string, fc_pool->string_length);
#elif defined(PMX)
		/* 部分匹配交叉 */
		pmx(fc_root, momma->string, daddy->string, fc_kid->string, fc_pool->string_length);
#elif defined(CX)
		/* 循环交叉 */
		cycle_diffs = cx(fc_root, momma->string, daddy->string, fc_kid->string, fc_pool->string_length, city_table);
		/* 突变孩子 */
		if (cycle_diffs == 0)
		{
			mutations++;
			geqo_mutation(fc_root, fc_kid->string, fc_pool->string_length);
		}
#elif defined(PX)
		/* 位置交叉 */
		px(fc_root, momma->string, daddy->string, fc_kid->string, fc_pool->string_length, city_table);
#elif defined(OX1)
		/* 顺序交叉 */
		ox1(fc_root, momma->string, daddy->string, fc_kid->string, fc_pool->string_length, city_table);
#elif defined(OX2)
		/* 顺序交叉 */
		ox2(fc_root, momma->string, daddy->string, fc_kid->string, fc_pool->string_length, city_table);
#endif


		/* 评估适应度 */
		fc_kid->worth = geqo_eval(fc_root, fc_kid->string, fc_pool->string_length);

		/* 根据其价值将孩子推入生活的荒野 */
		spread_chromo(fc_root, fc_kid, fc_pool);


#ifdef GEQO_DEBUG
		if (fc_status_interval && !(fc_generation % fc_status_interval))
			print_gen(stdout, fc_pool, fc_generation);
#endif

	}


#if defined(ERX)
#if defined(GEQO_DEBUG)
	if (fc_edge_failures != 0)
		elog(LOG, "[GEQO] failures: %d, average: %d",
			 fc_edge_failures, (int) fc_number_generations / fc_edge_failures);
	else
		elog(LOG, "[GEQO] no edge failures detected");
#else
	/* 压制某些编译器中变量设置但未使用的警告 */
	(void) fc_edge_failures;
#endif
#endif

#if defined(CX) && defined(GEQO_DEBUG)
	if (fc_mutations != 0)
		elog(LOG, "[GEQO] mutations: %d, generations: %d",
			 fc_mutations, fc_number_generations);
	else
		elog(LOG, "[GEQO] no mutations processed");
#endif

#ifdef GEQO_DEBUG
	print_pool(stdout, fc_pool, 0, fc_pool_size - 1);
#endif

#ifdef GEQO_DEBUG
	elog(DEBUG1, "GEQO best is %.2f after %d generations",
		 fc_pool->data[0].worth, fc_number_generations);
#endif


	/*
	 * 获取通过geqo处理的最便宜查询树；种群的第一个元素指示最佳查询树
	 */
	fc_best_tour = (Gene *) fc_pool->data[0].string;

	fc_best_rel = gimme_tree(fc_root, fc_best_tour, fc_pool->string_length);

	if (fc_best_rel == NULL)
		elog(ERROR, "geqo failed to make a valid plan");

	/* 调试：显示查询计划 */
#ifdef NOT_USED
#ifndef FDD
	print_plan(best_plan, fc_root);
#endif //end FDD
#endif

	/* ... 释放内存 */
	free_chromo(fc_root, fc_momma);
	free_chromo(fc_root, fc_daddy);

#if defined (ERX)
	free_edge_table(fc_root, fc_edge_table);
#elif defined(PMX)
	free_chromo(fc_root, fc_kid);
#elif defined(CX)
	free_chromo(fc_root, fc_kid);
	free_city_table(fc_root, city_table);
#elif defined(PX)
	free_chromo(fc_root, fc_kid);
	free_city_table(fc_root, city_table);
#elif defined(OX1)
	free_chromo(fc_root, fc_kid);
	free_city_table(fc_root, city_table);
#elif defined(OX2)
	free_chromo(fc_root, fc_kid);
	free_city_table(fc_root, city_table);
#endif

	free_pool(fc_root, fc_pool);

	/* ... 清除指向我们私有存储的根指针 */
	fc_root->join_search_private = NULL;

	return fc_best_rel;
}


/*
 * 返回配置的池大小或良好的默认值
 *
 * 默认值基于查询大小（关系数量）= 2^(QS+1)，
 * 但受到基于努力值的范围限制。
 */
static int fc_gimme_pool_size(int fc_nr_rel)
{
	double		fc_size;
	int			fc_minsize;
	int			fc_maxsize;

	/* 法律池的大小 *必须* 至少为 2，因此忽略选择 1 的尝试 */
	if (Geqo_pool_size >= 2)
		return Geqo_pool_size;

	fc_size = pow(2.0, fc_nr_rel + 1.0);

	fc_maxsize = 50 * Geqo_effort; /* 50 到 500 个个体 */
	if (fc_size > fc_maxsize)
		return fc_maxsize;

	fc_minsize = 10 * Geqo_effort; /* 10 到 100 个个体 */
	if (fc_size < fc_minsize)
		return fc_minsize;

	return (int) ceil(fc_size);
}


/*
 * 返回配置的世代数或一个好的默认值
 *
 * 默认值与池的大小相同，这确保了在运行结束之前，适应性较差的个体被排除在繁殖
 * 种群之外。
 */
static int fc_gimme_number_generations(int fc_pool_size)
{
	if (Geqo_generations > 0)
		return Geqo_generations;

	return fc_pool_size;
}
